#!/usr/bin/python
# encoding: utf-8

'''
Autor: Francisco do Ó
Nr: 5202
Email: franciscodoo@live.com.pt
'''

from linked_list import *
import sortAlgorithms
import time
import random
import sys

#sys.setrecursionlimit(10000)

class NoKD(object):
    '''
    Inicialização dos nós para a árvore k-dimensional.
    @param key: chave (coordenada) do ponto
    @param valor: valor, formato string
    '''
    def __init__(self, key, valor):
        self.key = key
        self.valor = valor
        self.parent = None
        self.left   = None
        self.right  = None
        pass

    #Verifica se o nó é folha
    def is_leaf(self):
        return (self.left.is_nil() and self.right.is_nil())
        pass

    #Verifica se o nó é nil
    def is_nil(self):
        return (self.key == 0 and self.valor == "")
        pass

    #metodo __str__ ~ nós
    def __str__(self):
        s = str(self.key) + ' - "' + str(self.valor)+'" - '
        s += '('
        if self.parent == None:
            s += 'Parent: ' + 'None'  + ', ' 
        else:
            s += 'Parent: ' + str(self.parent.key) + ', ' 
        if self.left == None:
            s += 'Left: ' + 'None'  + ', ' 
        else:
            s += 'Left: ' + str(self.left.key) + ', ' 
        if self.right == None:
            s += 'Right: ' + 'None' + ')' 
        else:
            s += 'Right: ' + str(self.right.key) + ')' 
        return s
    pass

################################################################
class KDNeighbourhood():
    """ 
    Procura do(s) vizinho(s) mais próximos de um determinado ponto
    """
    '''
    inicialização da instância
    @param sp: ponto inserido na pesquisa 
    '''
    def __init__(self, sp):
        self.sp = sp
        self.largest_distance = 0
        self.current_best = []

    '''
    distância (euclidiana) entre os dois pontos
    @param p1: Ponto 1 a comparar
    @param sp: Ponto 2 a comparar
    @return distance: ditância euclidiana entre os dois pontos 
    '''
    @staticmethod
    def distance(p1, p2):
        distance = 0
        axis = len(p1) #Assume que todos os pontos têm a mesma dimensão
        #O ciclo percorre todas coordenadas dos pontos p1 e p2
        #A distância é dada pela incrementação da diferença entre cada coordenada dos 2 pontos
        #(se os pontos tiverem 3 coordenadas (xyz) p1(x) é comparado com p2(x) e assim sucessivamente)
        #Por forma a evitar computação de raízes quadradas o resultado é elevado ao quadrado 
        for coord in range(axis):
            distance += (p1[coord] - p2[coord])**2 
            pass
        return distance
    '''
    Verifica se o ponto será adicionado como melhor vizinho actual ou não
    @param key: chave do nó
    @param valor: valor do nó
    '''
    def add(self, key,valor):
        #distância entre ponto inserido na pesquisa e o ponto a adicionar
        d = KDNeighbourhood.distance(key, self.sp)

        #verificar se o ponto será inserido na lista current_best
        for i, pt in enumerate(self.current_best):                
            #Se a distância do ponto que se encontra como melhor vizinho actual
            #For superior à distância do ponto a ser comparado actualmente (key) (até ao ponto inserido na pesquisa)
            #Este substitui o anterior como melhor vizinho
            if i < 1 and pt[1] > d:
                self.current_best.insert(i, [key, d,valor])
                self.n_distance = self.current_best[0][1]#(coord,dist)
                return
        #Caso contrário é adicionado ao fim da lista
        self.current_best.append([key, d,valor])
        self.n_distance = self.current_best[0][1]
    
    '''
    Devolve o resultado da pesquisa
    return: string com key e valor do melhor vizinho para o elemento introduzido
    '''
    def getNearestNeighbor(self):
        return 'O vizinho mais próximo é: ' +str(self.current_best[0][0]) +' - "'+ str(self.current_best[0][2])+'"'

################################################################
class ArvoreKD(object):
    '''
    Classe Arvore K-Dimensional 
    '''
    #inicialização da árvore
    def __init__(self):
        self.nil = NoKD(0, "")
        self.parent,self.left,self.right,self.root = [self.nil]*4

    '''    
    #Inserção dos nós na árvore binária
    def insertNB(self, z, depth=0):

        x = L.malloc(z.key,z.valor)
        L.insert(x)
        #inicialização dos apontadores para os nós pai, esquerda e direita
        z.parent = self.nil
        z.left = self.nil
        z.right = self.nil

        x = self.root #control var.Apontador de caminho.
        y = self.nil #control var. nó pai(parent) do nó x

        #Escolha do eixo(axis) baseado na profundidade(depth)
        #Por forma a que sejam comparadas as coordenadas devidas a cada nível

        k = len(z.key)#Assume que todos os pontos têm a mesma dimensão
        axis = depth % k 

        #Percorre a árvore comparando o valor da coordenada (determinada pela var axis)
        #do ponto a inserir, com o de cada nó
        while x != self.nil:
            axis = depth % k
            y = x
            #Se o valor da coordenada do nó a inserir for menor que o do nó actual
            #Segue-se para a esquerda
            if z.key[axis] < x.key[axis]:
                x = x.left
                depth +=1   
            #Caso contrário segue-se para a direita     
            else:
                x = x.right
                depth +=1

        z.parent = y
        if y == self.nil:
            self.root = z
        elif z.key[axis] < y.key[axis]:
            y.left = z
        #Caso contrário fica à direita    
        else:
            y.right = z
        '''

    '''
    Inserção dos nós na árvore binária
    @param z: nó a ser inserido
    @param depth: nível actual
    '''
    def insert(self, z, depth=0):
        #inserção dos valores na representação da memória
        x = L.malloc(z.key,z.valor)
        L.insert(x)
        #inicialização dos apontadores deste, para outros nós
        z.parent,z.left,z.right, z.left.left,z.left.right,z.right.right,z.right.lef = [self.nil]*7
        x = self.root #control var.Apontador de caminho.
        y = self.nil #control var. nó pai(parent) do nó x
        #Escolha do eixo(axis) baseado na profundidade(depth)
        #Por forma a que sejam comparadas as coordenadas devidas a cada nível
        k = len(z.key)#Assume que todos os pontos têm a mesma dimensão
        axis = depth % k 
        #Percorre a árvore comparando o valor da coordenada (determinada pela var axis)
        #do ponto a inserir, com o de cada nó
        while x != self.nil:
            axis = depth % k
            y = x
            #Se o valor do eixo da coordenada do nó a inserir for menor que o do nó actual
            if z.key[axis] < x.key[axis]:
                #...mas o nó actual já tem um filho à esquerda e à direita não tem nenhum
                if x.right.is_nil() and x.left != self.nil:
                    #O nó terá que ser desviado do seu caminho natural
                    x = x.right
                    depth +=1
                #...ou se apesar de ter dois filhos, o filho da esquerda possuir
                #mais filhos que o da direita
                elif x.right != self.nil and x.left != self.nil and \
                       x.left.left !=self.nil or x.left.right !=self.nil and \
                       x.right.left.is_nil() and x.right.right.is_nil():
                    #O nó terá que ser desviado do seu percurso
                    x = x.right
                    depth +=1
                #Caso contrário poderá seguir pela esquerda
                else:
                    x = x.left
                    depth +=1

            #Se o valor do eixo da coordenada do nó a inserir for igual ou superior à o do nó actual    
            else:
                #...mas o nó actual já tem um filho à direita e à esquerda não tem nenhum
                if x.left.is_nil() and x.right != self.nil:
                    #O nó terá que ser desviado do seu caminho natural
                    x = x.left
                    depth +=1
                #...ou se apesar de ter dois filhos, o filho da direita possuir
                #mais filhos que o da esquerda
                elif x.right != self.nil and x.left != self.nil and \
                       x.right.left !=self.nil or x.right.right !=self.nil and \
                       x.left.left.is_nil() and x.left.right.is_nil():
                    #O nó terá que ser desviado do seu percurso
                    x = x.left
                    depth +=1
                #Caso contrário poderá seguir pela direita
                else:
                    x = x.right
                    depth +=1

        z.parent = y
        #Adicionar nó na árvore
        #se y é nil árvore vazia então z fica como raiz
        if y == self.nil:
            self.root = z
        #se coordenada do nó a inserir no eixo actual for menor que a do seu parent
        # z fica à esquerda de y    
        elif z.key[axis] < y.key[axis]:
            if y.right.is_nil() and y.left != self.nil:
                y.right = z
            else:
                y.left = z
        #Caso contrário fica à direita    
        else:
            if y.left.is_nil() and y.right != self.nil:
                y.left = z
            else:
                y.right = z

    '''
    Devolve o sucessor de x
    @param x: nó a pesquisar o sucessor
    @return y: sucessor de x
    ''' 
    def sucessor(self, x):
        if x.right != self.nil:
            return minimum(x.right)
        y = x.parent
        while y != self.nil and x == y.right:
            x = y
            y = y.parent
        return y

    '''
    Devolve o o mais 'a esquerda da árvore)
    @param x: nó por onde se inicia a pesquisa
    @return x: valor mínimo
    '''
    def minimum(self, x):
        while x.left != self.nil:
            x = x.left
        return x

    '''
    Dada a eliminação de um elemento da árvore será
    Necessária a reconstrução de um conjunto de nós
    @param u: nó 1
    @param v: nó 2
    '''    
    def transplant(self, u, v):
        #se u nao tiver parent
        #v torna-se raiz
        if u.parent == self.nil:
            self.root = v
        #caso u esteja 'a esquerda do nó pai
        # v toma o lugar de u
        elif u == u.parent.left:
            u.parent.left = v
        #caso contrário o nó está à direita do pai
        #e v toma o seu lugar
        else:
            u.parent.right = v
        #se v nao for nil
        #o parent de u torna-se consequentemente pai de v
        if v != self.nil:
            v.parent = u.parent

    '''
    Eliminar um elemento da árvore
    @param z: Nó a eliminar
    '''
    def delete(self, z):
        #Elimina o valor da representação da memória(pilha)
        x = L.search(z.key,z.valor)
        L.delete(x)
        L.free(x)

        #Se à esquerda ou à direita de z não existir outro nó
        #só será necessário reconstruir o lado contrário
        #y vai com nil
        if z.left == self.nil:
            self.transplant(z, z.right)
        elif z.right == self.nil:
            self.transplant(z, z.left)
        #caso contrário será necessário calcular o val minimo d z
        #para efectuar transp do val com algum valor 'a sua dir.
        else:
            y = self.minimum(z.right)
            if y.parent != z:
                self.transplant(y, y.right)
                y.right = z.right
                y.right.parent = y
            #Efectua o transplante com base nas condições verificadas
            self.transplant(z, y)
            y.left = z.left
            y.left.parent = y
    pass

    '''
    Inicialização da pesquisa do vizinho mais próximo
    @param searchPoint: ponto a pesquisar, inserido pelo utilizador
    Imprime os resultados da pesquisa na consola
    '''
    def search(self, searchPoint):
        #Procura do vizinhos mais próximo
        print '\n**************** Procura do Vizinho Mais Próximo****************'
        print 'A procurar um vizinho para o ponto '+str(searchPoint)+'...'
        self.nds=0 #num nós percorrridos
        self.lfs=0 #num folhas
        def nearest_neighbor(node, searchPoint, depth, best_neighbours):

            if node.is_nil() : return None

            self.nds += 1
            # Se o nó for uma folha é adicionado como sendo o melhor vizinho actual
            if node.is_leaf():
                self.lfs += 1
                best_neighbours.add(node.key,node.valor)
                return None
            
            # eixo a comparar, com base na profundidade(depth) actual
            axis = depth % len(searchPoint)
            
            #compara o eixo (axis) do ponto inserido na procura com o nó actual, 
            # Determina qual a subárvore mais próxima e qual a mais distante
            if searchPoint[axis] < node.key[axis]: bst,wst = node.left, node.right          
            else: bst,wst = node.right, node.left

            # Chama o método recursivamente, até ser encontrado um nó folha
            nearest_neighbor(bst, searchPoint, depth+1, best_neighbours)

            #Verifica se o nó actual está mais próximo do ponto inserido na 
            #pesquisa comparativamente ao melhor actual
            best_neighbours.add(node.key,node.valor)
            
            #Verifica se poderão existir pontos na w_st (no eixo actual)
            #Que poderão estar mais próximos, comparativamente ao melhor vizinho actual
            if (node.key[axis] - searchPoint[axis])**2 < best_neighbours.n_distance:
                nearest_neighbor(wst, searchPoint, depth+1, best_neighbours)          
            return None

        #Se não existir árvore não à vizinhança para o ponto
        if self.root.is_nil():
         result='O ponto que inseriu afugentou toda a vizinhança... Construa uma nova árvore!'
         print 
        #Caso contrário a pesquisa é efectuada
        else:     
            neighbours = KDNeighbourhood(searchPoint[0])
            nearest_neighbor(self.root, searchPoint[0], depth=0, best_neighbours=neighbours)
            result = neighbours.getNearestNeighbor()
        
        #Resultado elemento +prox e nr de nos e folhas percorridos
        print result
        print 'Procurei '+str(self.nds)+' nós dos quais '+str(self.lfs)+' eram folhas'


    '''
    Ordenação da lista de pontos
    @param point_list:lista de pontos inserida pelo utilizador
    @param depth: nível actual
    @param new_list: lista que conterá os resultados ordenados
    @param sa: algoritmo de ordenação a ser utilizado
    @return new_list: lista com os dados ordenados
    '''
    @staticmethod   
    def sortNodes(point_list,depth=0,new_list=[], sa='timsort'):

        if not point_list:return None
        #determina eixo a comparar
        k = len(point_list[0][0]) 
        axis = depth % k
        #verifica qual o algoritmo que foi inserido pelo utilizador
        if sa == 'quicksort':           
            #print 'sorting list with quicksort'
            sortAlgorithms.QS(point_list, 0, len(point_list)-1, axis)

        elif sa =='mergesort':
            #print 'sorting list with mergesort'
            sortAlgorithms.MS(point_list, 0, len(point_list)-1, axis)

        elif sa == 'insertionsort':
            #print 'sorting list with insertionsort'
            sortAlgorithms.IS(point_list, axis)

        elif sa == 'bubblesort':
            #print 'sorting list with bubblesort'
            sortAlgorithms.BS(point_list, axis)

        elif sa == 'heapsort':
            #print 'sorting list with heapsort'
            sortAlgorithms.HS(point_list, axis)
        #caso nenhum tenha sido especificado ou este não tenha sido reconhecido
        #a lista é ordenada pelo timsort
        else: 
            #print 'sorting list with timsort'
            point_list.sort(key=lambda point: point[0][axis])    

        #procura a mediana de cada nível e inser-a numa nova lista
        median = len(point_list) // 2
        no = NoKD(point_list[median][0], point_list[median][1])
        new_list.append(no)

        #2 ev recursividade ~ stack overflow
        smaller =  ArvoreKD.sortNodes(point_list[0:median], depth+1,sa=sa)
        greater = ArvoreKD.sortNodes(point_list[median+1:], depth+1,sa=sa) 
        return new_list
    pass

    '''
    Adiciona uma lista de nós à árvore
    @param node_list: lista de nós a inserir na árvore
    '''
    def addNodeList(self, node_list):
        for node in node_list:
            self.insert(node)

    '''
    Ordena a árvore para ser imprimida 
    @param x: nó actual
    @param lista: listagem da árvore
    '''  
    def inorder_walk(self, x,lista):
            if x != self.nil:
                self.inorder_walk(x.left, lista)
                lista.append( x )
                self.inorder_walk(x.right, lista)

    '''
    imprime a árvore ordenada
    @return lista: listagem da árvore com os nós e respectivos apontadores
    '''
    def print_tree(self):
        lista = []
        self.inorder_walk(self.root,lista)
        print '\n************************ Árvore K-D ************************'
        for x in lista:
            print x



################################################################

'''********************EXEMPLO DE UTILIZAÇÃO********************'''
'''*************************************************************'''
'''**                                                         **'''
'''** É FUNDAMENTAL MANTER O FORMATO INDICADO EM CADA OPERAÇÃO**'''
'''**                                                         **'''
'''*************************************************************'''
'''*************************************************************'''

'''LISTA DE PONTOS A INSERIR NA ÁRVORE'''
point_list = [((1, 2, 3),"Ernesto Guevara"), ((1, 3, 4),"Fidel Castro"), ((-3, 2, 8),"Omar Torrijos"), 
              ((7, 8, 9), "Simón Bolívar"), ((-5, 2, 8),"Karl Marx" ), ((6, 2, 9), "Vladimir Lenin"), 
              ((6, 4, 7), "Mao Zedong" ), ((8, 2, 1), "Emiliano Zapata"),((9,9,9),"Jaime Roldós"),((-2,-1,0),"Phoolan Devi")]

'''LISTA TESTES: NUM. ALEATORIOS. LEN VARIAVEL'''
'''
nodelist= []
for i in range (500):
    c1=random.randint(-500,5000)
    c2=random.randint(-500,5000)
    c3=random.randint(-500,5000)
    pt=(c1,c2,c3)
    v="VALUE"
    no=(pt,v)
    nodelist.append(no)
'''

'''INICIALIZAÇÃO DA REPRESENTAÇÃO DA PILHA EM LISTA LIGADA'''
'''Atribuir SEMPRE um valor a N maior que o tamanho da lista a inserir'''
N=len(point_list)+5
L = LinkedList(N)

'''INICIALIZAÇÃO DA ÁRVORE'''
arv = ArvoreKD()

'''
ORDENAÇÃO DA LISTA DE PONTOS
   Para alterar algoritmo de ordenação mudar valor de sa para:
   bubblesort, insertionsort, mergesort, heapsort ou quicksort
   caso nao seja atribuído um valor a sa será utilizado o timsort.
'''
nos = arv.sortNodes(point_list,sa='timsort')

'''INSERÇÃO DA LISTA ORDENADA DE PONTOS'''
arv.addNodeList(nos)

'''INSERÇÃO DE ELEMENTOS SINGULARES NA ÁRVORE'''
n1=NoKD((2, 8, 9), "José Afonso")
arv.insert(n1)


'''REMOÇÃO DE ELEMENTOS DA ÁRVORE'''
arv.delete(n1)
#ou apagar nó da lista criada anteriormente
arv.delete(nos[2])

'''IMPRESSÃO DA PILHA NUMA LISTA LIGADA'''
L.printStack(N)

'''IMPRESSÃO DA ÁRVORE K-D'''
arv.print_tree()

'''PESQUISA DO VIZINHO MAIS PRÓXIMO'''
nearest = arv.search(searchPoint=((9, 4, 1),"Charles Baudelaire"))


